package com.leetcode.algorithm.y22.m08.w5;

import java.util.Arrays;

/**
 * 1005. K 次取反后最大化的数组和
 * 
 * https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
 * 
 * @author jie.deng
 *
 */
class Question1005Solution02 {

	// 贪心算法
	public int largestSumAfterKNegations(int[] nums, int k) {
		// 前提条件：
		// 局部最优：让绝对值大的负数变为正数
		// 全局最优：整个数组和达到最大

		Arrays.sort(nums);

		int len = nums.length;
		int cnt = 0;
		int idx = 0;
		int sum = 0;
		while (cnt < k && idx < len) {
			if (nums[idx] < 0) {
				cnt++;
				sum -= nums[idx];
			} else {
				sum += nums[idx];
			}
			idx++;
		}
		if (idx < len) {
			while (idx < len) {
				sum += nums[idx];
				idx++;
			}
		} else {
			if (((k - cnt) & 1) == 1) {
				// 找绝对值最小的
				if (nums[0] >= 0) {
					sum -= 2 * nums[0];
				} else if (nums[len - 1] <= 0) {
					sum += 2 * nums[len - 1];
				} else {
					int zeroIdx = searchInsertIdx(nums, 0);
					sum -= 2 * Math.min(Math.abs(nums[zeroIdx]), Math.abs(nums[zeroIdx - 1]));
				}
			}
		}
		return sum;
	}

	private int searchInsertIdx(int[] nums, int i) {
		int len = nums.length;
		int left = 0;
		int right = len - 1;
		// [left, right]
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (nums[mid] == 0) {
				return mid;
			} else if (nums[mid] > 0) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return right;
	}

}